package com.leetcode.程序员面试金典.hard;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 覃国强
 * @date 2022-02-16 18:42
 */
public class 面试题_17_21_直方图的水量 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
    int trap = solution.trap(height);
    System.out.println(trap);
  }

  static
  class Solution {

    public int trap(int[] height) {
      if (height == null || height.length < 2) {
        return 0;
      }
      int result = 0;
      int left = 0;
      int right = height.length - 1;
      int leftMax = 0;
      int rightMax = 0;
      while (left < right) {
        leftMax = Math.max(height[left], leftMax);
        rightMax = Math.max(height[right], rightMax);
        if (height[left] < height[right]) {
          result += (leftMax - height[left]);
          ++left;
        } else {
          result+= (rightMax - height[right]);
          --right;
        }
      }
      return result;
    }


    public int trap1(int[] height) {
      if (height == null || height.length < 2) {
        return 0;
      }

      int result = 0;
      Deque<Integer> decreaseStack = new ArrayDeque<>();
      for (int i = 0; i < height.length; ++i) {
        while (!decreaseStack.isEmpty() && height[i] > height[decreaseStack.peek()]) {
          Integer top = decreaseStack.pop();
          if (decreaseStack.isEmpty()) {
            break;
          }
          int left = decreaseStack.peek();
          int right = i;
          int curWidth = right - left - 1;
          int curHeight = Math.min(height[right], height[left]) - height[top];
          result += curWidth * curHeight;
        }
        decreaseStack.push(i);
      }
      return result;
    }

    public int trap0(int[] height) {
      if (height == null || height.length < 2) {
        return 0;
      }
      int[] rightMax = new int[height.length];
      rightMax[height.length - 1] = height[height.length - 1];
      for (int i = height.length - 2; i >= 0; --i) {
        rightMax[i] = Math.max(height[i], rightMax[i + 1]);
      }

      int result = 0;
      int leftMax = height[0];

      for (int i = 1; i < height.length; ++i) {
        leftMax = Math.max(leftMax, height[i]);
        int max = Math.min(leftMax, rightMax[i]);
        result += max - height[i];
      }

      return result;
    }
  }

}
